/*
 ------------------------------------------------------------------------------
 Copyright (C) 2006-2007 Team Blur.

 This file is part of the Quantum Engine source code.

 The Quantum Engine source code is free software; you can redistribute it and/or
 modify it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2 of the License, or (at your
 option) any later version.

 The Quantum Engine source code is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
 more details.

 You should have received a copy of the GNU General Public License along with
 the Quantum Engine source code; if not, write to the Free Software Foundation, Inc.,
 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 ------------------------------------------------------------------------------
*/


#include "cm_local.h"


typedef struct {
	bool		isPoint;
	int			contentMask;

	odVec3		start;
	odVec3		end;

	odBounds	bounds;
	odVec3		offsets[8];
	odVec3		extents;

	trace_t		trace;
} traceWork_t;


/*
 ==================
 CM_TestInBrush
 ==================
*/
static void CM_TestInBrush (traceWork_t *tw, cmBrush_t *brush){

	cmBrushSide_t	*side;
	odPlane			*plane;
	float			dist;
	int				i;

	// Test the brush bounds
	if (!brush->bounds.IntersectsBounds(tw->bounds))
			return;

	// The first six planes are the axial planes, so we only need to test the
	// remainder
	for (i = 6; i < brush->numSides; i++){
		side = &brush->sides[i];
		plane = side->plane;

		dist = plane->Distance(tw->start);

		// Adjust the plane distance appropriately for the box
		if (plane->type < PLANETYPE_NONAXIAL)
			dist += tw->offsets[plane->signBits][plane->type];
		else
			dist += tw->offsets[plane->signBits].Dot(plane->normal);

		// If completely in front of face, no intersection
		if (dist > 0.0f)
			return;
	}

	// Inside this brush
	tw->trace.allInside = true;
	tw->trace.startInside = true;
	tw->trace.fraction = 0.0f;

	tw->trace.c.contentFlags = brush->material->contentFlags;
}

/*
 ==================
 CM_TestInSurface
 ==================
*/
static void CM_TestInSurface (traceWork_t *tw, cmSurface_t *surface){

	cmSurfaceFacet_t	*facet;
	odPlane				*plane;
	odVec3				normal;
	float				dist;
	int					i, j;

	// Test the surface bounds
	if (!surface->bounds.IntersectsBounds(tw->bounds))
		return;

	// Test the surface facets
	for (i = 0, facet = surface->facets; i < surface->numFacets; i++, facet++){
		plane = &surface->planes[facet->facetPlane];

		dist = plane->Distance(tw->start);

		// Adjust the plane distance appropriately for the box
		if (plane->type < PLANETYPE_NONAXIAL)
			dist += tw->offsets[plane->signBits][plane->type];
		else
			dist += tw->offsets[plane->signBits].Dot(plane->normal);

		// If completely in front of face, no intersection
		if (dist > 0.0f)
			continue;

		for (j = 0; j < facet->numBorders; j++){
			plane = &surface->planes[facet->borderPlanes[j]];

			if (facet->borderInward & BIT(j)){
				normal = -plane->normal;
				dist = -plane->dist;
			}
			else {
				normal = plane->normal;
				dist = plane->dist;
			}

			// This works even though the plane might be flipped because the
			// box is centered
			dist += M_Fabs(tw->offsets[plane->signBits].Dot(normal));

			if (tw->start.Dot(normal) - dist > 0.0f)
				break;
		}

		if (j != facet->numBorders)
			continue;

		// Inside this surface facet
		tw->trace.allInside = true;
		tw->trace.startInside = true;
		tw->trace.fraction = 0.0f;

		tw->trace.c.contentFlags = surface->material->contentFlags;

		return;
	}
}

/*
 ==================
 CM_TestInLeaf
 ==================
*/
static void CM_TestInLeaf (traceWork_t *tw, cmLeaf_t *leaf){

	cmBrush_t	*brush;
	cmSurface_t	*surface;
	int			i, num;

	cm_stats.leafTests++;		// Optimize counter

	// Test against all brushes in the leaf
	for (i = 0; i < leaf->numLeafBrushes; i++){
		num = cm.leafBrushes[leaf->firstLeafBrush + i];
		brush = &cm.brushes[num];

		if (brush->traceCount == cm.traceCount)
			continue;		// Already checked this brush in another leaf
		brush->traceCount = cm.traceCount;

		if (!(brush->material->contentFlags & tw->contentMask))
			continue;		// Doesn't have the contents we're looking for

		cm_stats.brushTests++;		// Optimize counter

		// Test against the brush
		CM_TestInBrush(tw, brush);

		if (!tw->trace.fraction)
			return;
	}

	// No point test against surfaces
	if (tw->isPoint)
		return;

	// Test against all surfaces in the leaf
	if (cm_skipSurfaces->integerValue)
		return;

	for (i = 0; i < leaf->numLeafSurfaces; i++){
		num = cm.leafSurfaces[leaf->firstLeafSurface + i];
		surface = cm.surfaces[num];

		if (!surface)
			continue;		// No collision data

		if (surface->traceCount == cm.traceCount)
			continue;		// Already checked this surface in another leaf
		surface->traceCount = cm.traceCount;

		if (!(surface->material->contentFlags & tw->contentMask))
			continue;		// Doesn't have the contents we're looking for

		if (surface->type == ST_PATCH)
			cm_stats.patchTests++;		// Optimize counter
		if (surface->type == ST_TRISOUP)
			cm_stats.trisoupTests++;	// Optimize counter

		// Test against the surface
		CM_TestInSurface(tw, surface);

		if (!tw->trace.fraction)
			return;
	}
}

/*
 ==================
 CM_TestInInlineModel
 ==================
*/
static void CM_TestInInlineModel (traceWork_t *tw, cmInlineModel_t *model){

	// If the model has multiple brushes and/or surfaces
	if (model->leaf.numLeafBrushes + model->leaf.numLeafSurfaces > 1){
		// If it doesn't have the contents we're looking for, ignore it
		if (!(model->leaf.contentFlags & tw->contentMask))
			return;

		// If completely outside the model bounds, ignore it
		if (!model->bounds.IntersectsBounds(tw->bounds))
			return;
	}

	// Test against all brushes and surfaces in the model
	CM_TestInLeaf(tw, &model->leaf);
}

/*
 ==================
 CM_TestInStaticModel
 ==================
*/
static void CM_TestInStaticModel (traceWork_t *tw, cmStaticModel_t *model){

	cmSurface_t	*surface;
	int			i;

	// No point test against surfaces
	if (tw->isPoint)
		return;

	// If the model has multiple surfaces
	if (model->numSurfaces > 1){
		// If it doesn't have the contents we're looking for, ignore it
		if (!(model->contentFlags & tw->contentMask))
			return;

		// If completely outside the model bounds, ignore it
		if (!model->bounds.IntersectsBounds(tw->bounds))
			return;
	}

	// Test against all surfaces in the model
	if (cm_skipSurfaces->integerValue)
		return;

	for (i = 0, surface = model->surfaces; i < model->numSurfaces; i++, surface++){
		if (!(surface->material->contentFlags & tw->contentMask))
			continue;		// Doesn't have the contents we're looking for

		cm_stats.meshTests++;		// Optimize counter

		// Test against the surface
		CM_TestInSurface(tw, surface);

		if (!tw->trace.fraction)
			return;
	}
}

/*
 ==================
 CM_TestInDynamicModel
 ==================
*/
static void CM_TestInDynamicModel (traceWork_t *tw, cmDynamicModel_t *model){

	cmTriangleSurface_t	*surface;
	int					i, j;

	// No point test against surfaces
	if (tw->isPoint)
		return;

	// If the model has multiple surfaces
	if (model->numSurfaces > 1){
		// If it doesn't have the contents we're looking for, ignore it
		if (!(model->contentFlags & tw->contentMask))
			return;

		// If completely outside the model bounds, ignore it
		if (!model->bounds.IntersectsBounds(tw->bounds))
			return;
	}

	// Test against all surfaces in the model
	if (cm_skipSurfaces->integerValue)
		return;

	for (i = 0, surface = model->surfaces; i < model->numSurfaces; i++, surface++){
		if (!(surface->material->contentFlags & tw->contentMask))
			continue;		// Doesn't have the contents we're looking for

		cm_stats.meshTests++;		// Optimize counter

		// Test the surface bounds
		if (!surface->bounds.IntersectsBounds(tw->bounds))
			continue;

		// Test the surface vertices
		for (j = 0; j < surface->numVertices; j++){
			if (tw->bounds.ContainsPoint(surface->transformedXyz[j]))
				break;
		}

		if (j == surface->numVertices)
			continue;

		// Inside this surface
		tw->trace.allInside = true;
		tw->trace.startInside = true;
		tw->trace.fraction = 0.0f;

		tw->trace.c.contentFlags = surface->material->contentFlags;

		return;
	}
}

/*
 ==================
 CM_TestPointInWorld
 ==================
*/
static void CM_TestPointInWorld (traceWork_t *tw, int num){

	cmNode_t	*node;
	cmLeaf_t	*leaf;
	int			side;

	while (1){
		// If < 0, we are in a leaf node
		if (num < 0){
			leaf = &cm.leafs[-1 - num];

			if (!(leaf->contentFlags & tw->contentMask))
				return;			// Doesn't have the contents we're looking for

			// Test against all brushes and surfaces in the leaf
			CM_TestInLeaf(tw, leaf);
			return;
		}

		// Find which side of the node we are on
		node = &cm.nodes[num];

		side = node->plane->PointOnSide(tw->start);

		// Go down the appropriate side
		if (side == PLANESIDE_FRONT)
			num = node->children[0];
		else
			num = node->children[1];
	}
}

/*
 ==================
 CM_TestBoxInWorld
 ==================
*/
static void CM_TestBoxInWorld (traceWork_t *tw, int num){

	cmNode_t	*node;
	cmLeaf_t	*leaf;
	int			side;

	if (!tw->trace.fraction)
		return;

	// If < 0, we are in a leaf node
	if (num < 0){
		leaf = &cm.leafs[-1 - num];

		if (!(leaf->contentFlags & tw->contentMask))
			return;			// Doesn't have the contents we're looking for

		// Test against all brushes and surfaces in the leaf
		CM_TestInLeaf(tw, leaf);
		return;
	}

	// Find which side of the node we are on
	node = &cm.nodes[num];

	side = node->plane->BoundsOnSide(tw->bounds);

	// Go down the appropriate sides
	if (side == PLANESIDE_FRONT){
		CM_TestBoxInWorld(tw, node->children[0]);
		return;
	}
	if (side == PLANESIDE_BACK){
		CM_TestBoxInWorld(tw, node->children[1]);
		return;
	}

	CM_TestBoxInWorld(tw, node->children[0]);
	CM_TestBoxInWorld(tw, node->children[1]);
}

/*
 ==================
 CM_TraceIntersectsBounds

 This function determines if a trace passes through the bounds of a model or
 surface.

 If this function returns false, the model or surface should be skipped
 completely, which can save significant time on complex collision surfaces.

 A box trace through a dynamic model will specify the material parameter so
 that the trace structure is filled accordingly (we don't support box traces
 with dynamic models at the moment).
 ==================
*/
static bool CM_TraceIntersectsBounds (traceWork_t *tw, odPlane sides[6], cmMaterial_t *material){

	odPlane	*plane, *clipPlane;
	bool	startOut;
	float	frac, enterFrac, leaveFrac;
	float	dist, d1, d2;
	int		i;

	startOut = false;

	enterFrac = -1.0f;
	leaveFrac = 1.0f;

	for (i = 0; i < 6; i++){
		plane = &sides[i];

		d1 = plane->Distance(tw->start);
		d2 = plane->Distance(tw->end);

		// Adjust the plane distance appropriately for the box
		if (plane->type < PLANETYPE_NONAXIAL)
			dist = tw->offsets[plane->signBits][plane->type];
		else
			dist = tw->offsets[plane->signBits].Dot(plane->normal);

		d1 += dist;
		d2 += dist;

		if (d1 > 0.0f)
			startOut = true;	// Start point is not inside the bounds

		// If completely in front of face, no intersection with the entire
		// bounds
		if (d1 > 0.0f && (d2 >= CM_CLIP_EPSILON || d2 >= d1))
			return false;

		// If it doesn't cross the plane, the plane isn't relevant
		if (d1 <= 0.0f && d2 <= 0.0f)
			continue;

		// Crosses face
		if (d1 > d2){
			// Enter
			frac = (d1 - CM_CLIP_EPSILON) / (d1 - d2);
			if (frac < 0.0f)
				frac = 0.0f;

			if (frac > enterFrac){
				enterFrac = frac;

				clipPlane = plane;
			}
		}
		else {
			// Leave
			frac = (d1 + CM_CLIP_EPSILON) / (d1 - d2);
			if (frac > 1.0f)
				frac = 1.0f;

			if (frac < leaveFrac)
				leaveFrac = frac;
		}
	}

	if (!startOut)
		return true;	// Start point was inside the bounds

	if (enterFrac >= 0.0f && enterFrac < leaveFrac){
		if (enterFrac < tw->trace.fraction){
			if (material){
				tw->trace.fraction = enterFrac;

				tw->trace.c.material = material->name;
				tw->trace.c.surfaceFlags = material->surfaceFlags;
				tw->trace.c.contentFlags = material->contentFlags;

				tw->trace.c.plane = *clipPlane;
			}

			return true;
		}
	}

	return false;
}

/*
 ==================
 CM_TraceThroughBrush
 ==================
*/
static void CM_TraceThroughBrush (traceWork_t *tw, cmBrush_t *brush){

	cmBrushSide_t	*side, *leadSide;
	odPlane			*plane, *clipPlane;
	bool			startOut, endOut;
	float			frac, enterFrac, leaveFrac;
	float			dist, d1, d2;
	int				i;

	startOut = false;
	endOut = false;

	enterFrac = -1.0f;
	leaveFrac = 1.0f;

	// Compare the trace against all planes of the brush.
	// Find the latest time the trace crosses a plane towards the interior and
	// the earliest time the trace crosses a plane towards the exterior.
	for (i = 0; i < brush->numSides; i++){
		side = &brush->sides[i];
		plane = side->plane;

		d1 = plane->Distance(tw->start);
		d2 = plane->Distance(tw->end);

		// Adjust the plane distance appropriately for the box
		if (plane->type < PLANETYPE_NONAXIAL)
			dist = tw->offsets[plane->signBits][plane->type];
		else
			dist = tw->offsets[plane->signBits].Dot(plane->normal);

		d1 += dist;
		d2 += dist;

		if (d1 > 0.0f)
			startOut = true;	// Start point is not inside the brush
		if (d2 > 0.0f)
			endOut = true;		// End point is not inside the brush

		// If completely in front of face, no intersection with the entire
		// brush
		if (d1 > 0.0f && (d2 >= CM_CLIP_EPSILON || d2 >= d1))
			return;

		// If it doesn't cross the plane, the plane isn't relevant
		if (d1 <= 0.0f && d2 <= 0.0f)
			continue;

		// Crosses face
		if (d1 > d2){
			// Enter
			frac = (d1 - CM_CLIP_EPSILON) / (d1 - d2);
			if (frac < 0.0f)
				frac = 0.0f;

			if (frac > enterFrac){
				enterFrac = frac;

				leadSide = side;
				clipPlane = plane;
			}
		}
		else {
			// Leave
			frac = (d1 + CM_CLIP_EPSILON) / (d1 - d2);
			if (frac > 1.0f)
				frac = 1.0f;

			if (frac < leaveFrac)
				leaveFrac = frac;
		}
	}

	if (!startOut){
		// Start point was inside the brush
		tw->trace.startInside = true;

		if (!endOut){
			// End point was inside the brush
			tw->trace.allInside = true;
			tw->trace.fraction = 0.0f;

			tw->trace.c.contentFlags = brush->material->contentFlags;
		}

		return;
	}

	if (enterFrac >= 0.0f && enterFrac < leaveFrac){
		if (enterFrac < tw->trace.fraction){
			tw->trace.fraction = enterFrac;

			tw->trace.c.material = leadSide->material->name;
			tw->trace.c.surfaceFlags = leadSide->material->surfaceFlags;
			tw->trace.c.contentFlags = brush->material->contentFlags;

			tw->trace.c.plane = *clipPlane;
		}
	}
}

/*
 ==================
 CM_CheckFacetPlane
 ==================
*/
static bool CM_CheckFacetPlane (const odVec3 &normal, float dist, int type, const odVec3 &start, const odVec3 &end, float *enterFrac, float *leaveFrac, bool *hit){

	float	d1, d2;
	float	frac;

	*hit = false;

	if (type < PLANETYPE_NONAXIAL){
		d1 = start[type] - dist;
		d2 = end[type] - dist;
	}
	else {
		d1 = start.Dot(normal) - dist;
		d2 = end.Dot(normal) - dist;
	}

	// If completely in front of face, no intersection with the entire facet
	if (d1 > 0.0f && (d2 >= CM_CLIP_EPSILON || d2 >= d1))
		return false;

	// If it doesn't cross the plane, the plane isn't relevant
	if (d1 <= 0.0f && d2 <= 0.0f)
		return true;

	// Crosses face
	if (d1 > d2){
		// Enter
		frac = (d1 - CM_CLIP_EPSILON) / (d1 - d2);
		if (frac < 0.0f)
			frac = 0.0f;

		// Always favor previous plane hits and thus also the surface plane hit
		if (frac > *enterFrac){
			*enterFrac = frac;

			*hit = true;
		}
	}
	else {
		// Leave
		frac = (d1 + CM_CLIP_EPSILON) / (d1 - d2);
		if (frac > 1.0f)
			frac = 1.0f;

		if (frac < *leaveFrac)
			*leaveFrac = frac;
	}

	return true;
}

/*
 ==================
 CM_TraceThroughSurface
 ==================
*/
static void CM_TraceThroughSurface (traceWork_t *tw, cmSurface_t *surface){

	cmSurfaceFacet_t	*facet;
	odPlane				*plane;
	float				enterFrac, leaveFrac;
	odVec3				normal;
	float				dist;
	bool				hit;
	int					hitPlane;
	int					i, j;

	// If the surface bounds aren't intersected, ignore it
	if (!CM_TraceIntersectsBounds(tw, surface->sides, NULL))
		return;

	// Check the surface facets
	for (i = 0, facet = surface->facets; i < surface->numFacets; i++, facet++){
		enterFrac = -1.0f;
		leaveFrac = 1.0f;

		plane = &surface->planes[facet->facetPlane];

		// Adjust the plane distance appropriately for the box
		if (plane->type < PLANETYPE_NONAXIAL)
			dist = tw->offsets[plane->signBits][plane->type];
		else
			dist = tw->offsets[plane->signBits].Dot(plane->normal);

		if (!CM_CheckFacetPlane(plane->normal, plane->dist - dist, plane->type, tw->start, tw->end, &enterFrac, &leaveFrac, &hit))
			continue;

		if (hit)
			hitPlane = -1;

		for (j = 0; j < facet->numBorders; j++){
			plane = &surface->planes[facet->borderPlanes[j]];

			if (facet->borderInward & BIT(j)){
				normal = -plane->normal;
				dist = -plane->dist;
			}
			else {
				normal = plane->normal;
				dist = plane->dist;
			}

			// This works even though the plane might be flipped because the
			// box is centered
			dist += M_Fabs(tw->offsets[plane->signBits].Dot(normal));

			if (!CM_CheckFacetPlane(normal, dist, PLANETYPE_NONAXIAL, tw->start, tw->end, &enterFrac, &leaveFrac, &hit))
				break;

			if (hit){
				// Never clip against the back side
				if (j == facet->numBorders - 1)
					break;

				hitPlane = j;
			}
		}

		if (j != facet->numBorders)
			continue;

		if (enterFrac >= 0.0f && enterFrac < leaveFrac){
			if (enterFrac < tw->trace.fraction){
				tw->trace.fraction = enterFrac;

				tw->trace.c.material = surface->material->name;
				tw->trace.c.surfaceFlags = surface->material->surfaceFlags;
				tw->trace.c.contentFlags = surface->material->contentFlags;

				if (hitPlane == -1){
					plane = &surface->planes[facet->facetPlane];

					tw->trace.c.plane = *plane;
				}
				else {
					plane = &surface->planes[facet->borderPlanes[hitPlane]];

					if (facet->borderInward & BIT(hitPlane))
						tw->trace.c.plane.Set(-plane->normal, -plane->dist);
					else
						tw->trace.c.plane.Set(plane->normal, plane->dist);

					tw->trace.c.plane.SetType();
					tw->trace.c.plane.SetSignBits();
				}

				if (!tw->trace.fraction)
					return;
			}
		}
	}
}

/*
 ==================
 CM_TraceThroughLeaf
 ==================
*/
static void CM_TraceThroughLeaf (traceWork_t *tw, cmLeaf_t *leaf){

	cmBrush_t	*brush;
	cmSurface_t	*surface;
	int			i, num;

	cm_stats.leafTraces++;		// Optimize counter

	// Trace through all the brushes in the leaf
	for (i = 0; i < leaf->numLeafBrushes; i++){
		num = cm.leafBrushes[leaf->firstLeafBrush + i];
		brush = &cm.brushes[num];

		if (brush->traceCount == cm.traceCount)
			continue;		// Already checked this brush in another leaf
		brush->traceCount = cm.traceCount;

		if (!(brush->material->contentFlags & tw->contentMask))
			continue;		// Doesn't have the contents we're looking for

		cm_stats.brushTraces++;		// Optimize counter

		// Trace through the brush
		CM_TraceThroughBrush(tw, brush);

		if (!tw->trace.fraction)
			return;
	}

	// Trace through all the surfaces in the leaf
	if (cm_skipSurfaces->integerValue)
		return;

	for (i = 0; i < leaf->numLeafSurfaces; i++){
		num = cm.leafSurfaces[leaf->firstLeafSurface + i];
		surface = cm.surfaces[num];

		if (!surface)
			continue;		// No collision data

		if (surface->traceCount == cm.traceCount)
			continue;		// Already checked this surface in another leaf
		surface->traceCount = cm.traceCount;

		if (!(surface->material->contentFlags & tw->contentMask))
			continue;		// Doesn't have the contents we're looking for

		if (surface->type == ST_PATCH)
			cm_stats.patchTraces++;		// Optimize counter
		if (surface->type == ST_TRISOUP)
			cm_stats.trisoupTraces++;	// Optimize counter

		// Trace through the surface
		CM_TraceThroughSurface(tw, surface);

		if (!tw->trace.fraction)
			return;
	}
}

/*
 ==================
 CM_TraceThroughInlineModel
 ==================
*/
static void CM_TraceThroughInlineModel (traceWork_t *tw, cmInlineModel_t *model){

	// If the model has multiple brushes and/or surfaces
	if (model->leaf.numLeafBrushes + model->leaf.numLeafSurfaces > 1){
		// If it doesn't have the contents we're looking for, ignore it
		if (!(model->leaf.contentFlags & tw->contentMask))
			return;

		// If the model bounds aren't intersected, ignore it
		if (!CM_TraceIntersectsBounds(tw, model->sides, NULL))
			return;
	}

	// Trace through all the brushes and surfaces in the model
	CM_TraceThroughLeaf(tw, &model->leaf);
}

/*
 ==================
 CM_TraceThroughStaticModel
 ==================
*/
static void CM_TraceThroughStaticModel (traceWork_t *tw, cmStaticModel_t *model){

	cmSurface_t	*surface;
	int			i;

	// If the model has multiple surfaces
	if (model->numSurfaces > 1){
		// If it doesn't have the contents we're looking for, ignore it
		if (!(model->contentFlags & tw->contentMask))
			return;

		// If the model bounds aren't intersected, ignore it
		if (!CM_TraceIntersectsBounds(tw, model->sides, NULL))
			return;
	}

	// Trace through all the surfaces in the model
	if (cm_skipSurfaces->integerValue)
		return;

	for (i = 0, surface = model->surfaces; i < model->numSurfaces; i++, surface++){
		if (!(surface->material->contentFlags & tw->contentMask))
			continue;		// Doesn't have the contents we're looking for

		cm_stats.meshTraces++;		// Optimize counter

		// Trace through the surface
		CM_TraceThroughSurface(tw, surface);

		if (!tw->trace.fraction)
			return;
	}
}

/*
 ==================
 CM_TraceThroughDynamicModel
 ==================
*/
static void CM_TraceThroughDynamicModel (traceWork_t *tw, cmDynamicModel_t *model){

	cmTriangleSurface_t	*surface;
	odPlane				*facePlane, *edgePlane;
	odVec3				mid;
	float				d1, d2;
	float				frac;
	int					i, j;

	// If the model has multiple surfaces
	if (model->numSurfaces > 1){
		// If it doesn't have the contents we're looking for, ignore it
		if (!(model->contentFlags & tw->contentMask))
			return;

		// If the model bounds aren't intersected, ignore it
		if (!CM_TraceIntersectsBounds(tw, model->sides, NULL))
			return;
	}

	// Trace through all the surfaces in the model
	if (cm_skipSurfaces->integerValue)
		return;

	for (i = 0, surface = model->surfaces; i < model->numSurfaces; i++, surface++){
		if (!(surface->material->contentFlags & tw->contentMask))
			continue;		// Doesn't have the contents we're looking for

		cm_stats.meshTraces++;		// Optimize counter

		// If the surface bounds aren't intersected, ignore it (box traces are
		// special)
		if (tw->isPoint){
			if (!CM_TraceIntersectsBounds(tw, surface->sides, NULL))
				continue;
		}
		else {
			CM_TraceIntersectsBounds(tw, surface->sides, surface->material);
			continue;
		}

		// Check the surface triangles
		for (j = 0, facePlane = surface->facePlanes, edgePlane = surface->edgePlanes; j < surface->numTriangles; j++, facePlane++, edgePlane += 3){
			d1 = facePlane->Distance(tw->start);
			d2 = facePlane->Distance(tw->end);

			// If completely in front of face, no intersection with the entire
			// triangle
			if (d1 > 0.0f && (d2 >= CM_CLIP_EPSILON || d2 >= d1))
				continue;

			// If it doesn't cross the plane, the plane isn't relevant
			if (d1 <= 0.0f && d2 <= 0.0f)
				continue;

			// If it doesn't cross the plane towards the interior, the plane
			// isn't relevant
			if (d1 < d2)
				continue;

			// Crosses face
			frac = (d1 - CM_CLIP_EPSILON) / (d1 - d2);
			if (frac < 0.0f)
				frac = 0.0f;

			if (tw->trace.fraction <= frac)
				continue;		// Already hit something nearer

			// If the intersection point is completely in front of an edge
			// plane, the triangle wasn't hit
			mid.Lerp(tw->start, tw->end, frac);

			if (edgePlane[0].Distance(mid) > CM_CLIP_EPSILON)
				continue;
			if (edgePlane[1].Distance(mid) > CM_CLIP_EPSILON)
				continue;
			if (edgePlane[2].Distance(mid) > CM_CLIP_EPSILON)
				continue;

			// We hit this surface triangle
			tw->trace.fraction = frac;

			tw->trace.c.material = surface->material->name;
			tw->trace.c.surfaceFlags = surface->material->surfaceFlags;
			tw->trace.c.contentFlags = surface->material->contentFlags;

			tw->trace.c.plane = *facePlane;

			if (!tw->trace.fraction)
				return;
		}
	}
}

/*
 ==================
 CM_TraceThroughWorld

 Traverse all the contacted leaves from the start to the end position.
 If the trace is a point, they will be exactly in order, but for larger trace
 volumes it is posible to hit something in a later leaf with a smaller
 intercept fraction.
 ==================
*/
static void CM_TraceThroughWorld (traceWork_t *tw, int num, const odVec3 &p1, const odVec3 &p2, float p1f, float p2f){

	cmNode_t	*node;
	cmLeaf_t	*leaf;
	odPlane		*plane;
	odVec3		mid;
	float		dist, d1, d2;
	float		frac1, frac2;
	float		offset;
	int			side;

	if (tw->trace.fraction <= p1f)
		return;		// Already hit something nearer

	// If < 0, we are in a leaf node
	if (num < 0){
		leaf = &cm.leafs[-1 - num];

		if (!(leaf->contentFlags & tw->contentMask))
			return;			// Doesn't have the contents we're looking for

		// Trace through the leaf
		CM_TraceThroughLeaf(tw, leaf);
		return;
	}

	// Find the point distances to the separating plane
	node = &cm.nodes[num];
	plane = node->plane;

	d1 = plane->Distance(p1);
	d2 = plane->Distance(p2);

	// Find the offset for the size of the box
	if (tw->isPoint)
		offset = 0.0f;
	else {
		if (plane->type < PLANETYPE_NONAXIAL)
			offset = tw->extents[plane->type];
		else
			offset = M_Fabs(tw->extents.x * plane->normal.x) + M_Fabs(tw->extents.y * plane->normal.y) + M_Fabs(tw->extents.z * plane->normal.z);
	}

	// See which sides we need to consider
	if (d1 >= offset && d2 >= offset){
		CM_TraceThroughWorld(tw, node->children[0], p1, p2, p1f, p2f);
		return;
	}
	if (d1 < -offset && d2 < -offset){
		CM_TraceThroughWorld(tw, node->children[1], p1, p2, p1f, p2f);
		return;
	}

	// Put the crosspoint CM_CLIP_EPSILON units on the near side
	if (d1 > d2){
		dist = 1.0f / (d1 - d2);

		frac1 = (d1 + offset + CM_CLIP_EPSILON) * dist;
		frac2 = (d1 - offset - CM_CLIP_EPSILON) * dist;

		side = 0;
	}
	else if (d1 < d2){
		dist = 1.0f / (d1 - d2);

		frac1 = (d1 - offset + CM_CLIP_EPSILON) * dist;
		frac2 = (d1 + offset + CM_CLIP_EPSILON) * dist;

		side = 1;
	}
	else {
		frac1 = 1.0f;
		frac2 = 0.0f;

		side = 0;
	}

	// Move up to the node
	if (frac1 <= 0.0f)
		CM_TraceThroughWorld(tw, node->children[side], p1, p1, p1f, p1f);
	else if (frac1 >= 1.0f)
		CM_TraceThroughWorld(tw, node->children[side], p1, p2, p1f, p2f);
	else {
		mid.Lerp(p1, p2, frac1);

		CM_TraceThroughWorld(tw, node->children[side], p1, mid, p1f, p1f + (p2f - p1f) * frac1);
	}

	// Go past the node
	if (frac2 <= 0.0f)
		CM_TraceThroughWorld(tw, node->children[side^1], p1, p2, p1f, p2f);
	else if (frac2 >= 1.0f)
		CM_TraceThroughWorld(tw, node->children[side^1], p2, p2, p2f, p2f);
	else {
		mid.Lerp(p1, p2, frac2);

		CM_TraceThroughWorld(tw, node->children[side^1], mid, p2, p1f + (p2f - p1f) * frac2, p2f);
	}
}

/*
 ==================
 CM_Trace
 ==================
*/
trace_t CM_Trace (const odVec3 &start, const odVec3 &end, const odBounds &bounds, int contentMask, clipModel_t *model, const odVec3 &modelOrigin, const odMat3 &modelAxis){

	traceWork_t	tw;
	odBounds	size;
	odVec3		tmp, offset;
	bool		rotated;
	int			i;

	if (!cm.loaded)
		Com_Error(false, "CM_Trace: map not loaded");

	cm.traceCount++;		// For multi-check avoidance

	// Fill in a default trace
	memset(&tw.trace, 0, sizeof(trace_t));
	tw.trace.fraction = 1.0f;

	tw.contentMask = contentMask;

	// Adjust so that the bounds are always symetric, which avoids some
	// complications with plane expanding of rotated models
	offset = bounds.GetCenter();

	if (offset.IsCleared()){
		tw.start = start;
		tw.end = end;

		size = bounds;
	}
	else {
		tw.start = start + offset;
		tw.end = end + offset;

		size = bounds - offset;
	}

	// Transform into local space
	if (modelAxis.IsIdentity()){
		rotated = false;

		tw.start -= modelOrigin;
		tw.end -= modelOrigin;
	}
	else {
		rotated = true;

		modelAxis.ProjectVector(tw.start - modelOrigin, tw.start);
		modelAxis.ProjectVector(tw.end - modelOrigin, tw.end);
	}

	// Check for point special case
	if (size.IsZeroed())
		tw.isPoint = true;
	else
		tw.isPoint = false;

	// Expand size for epsilons
	if (tw.isPoint)
		size.Expand(CM_CLIP_EPSILON);
	else
		size.Expand(CM_BOX_EPSILON);

	// Calculate bounds
	for (i = 0; i < 3; i++){
		if (tw.start[i] < tw.end[i]){
			tw.bounds[0][i] = tw.start[i] + size[0][i];
			tw.bounds[1][i] = tw.end[i] + size[1][i];
		}
		else {
			tw.bounds[0][i] = tw.end[i] + size[0][i];
			tw.bounds[1][i] = tw.start[i] + size[1][i];
		}
	}

	// Set offsets to appropriate corners from origin
	tw.offsets[0].Set(size[0][0], size[0][1], size[0][2]);
	tw.offsets[1].Set(size[1][0], size[0][1], size[0][2]);
	tw.offsets[2].Set(size[0][0], size[1][1], size[0][2]);
	tw.offsets[3].Set(size[1][0], size[1][1], size[0][2]);
	tw.offsets[4].Set(size[0][0], size[0][1], size[1][2]);
	tw.offsets[5].Set(size[1][0], size[0][1], size[1][2]);
	tw.offsets[6].Set(size[0][0], size[1][1], size[1][2]);
	tw.offsets[7].Set(size[1][0], size[1][1], size[1][2]);

	// Set extents
	tw.extents = size[1];

	// Check for position test special case
	if (start == end){
		cm_stats.tests++;		// Optimize counter

		// Test position against the model or world
		if (model){
			if (cm_skipModels->integerValue){
				tw.trace.endPos = start;

				return tw.trace;
			}

			switch (model->type){
			case CLIP_MODEL_INLINE:
				CM_TestInInlineModel(&tw, (cmInlineModel_t *)model->data);
				break;
			case CLIP_MODEL_STATIC:
				CM_TestInStaticModel(&tw, (cmStaticModel_t *)model->data);
				break;
			case CLIP_MODEL_DYNAMIC:
				CM_TestInDynamicModel(&tw, (cmDynamicModel_t *)model->data);
				break;
			}
		}
		else {
			if (tw.isPoint)
				CM_TestPointInWorld(&tw, 0);
			else
				CM_TestBoxInWorld(&tw, 0);
		}

		// Copy the original, unmodified start
		tw.trace.endPos = start;

		return tw.trace;
	}

	cm_stats.traces++;		// Optimize counter

	// Sweep through the model or world
	if (model){
		if (cm_skipModels->integerValue){
			tw.trace.endPos = end;

			return tw.trace;
		}

		switch (model->type){
		case CLIP_MODEL_INLINE:
			CM_TraceThroughInlineModel(&tw, (cmInlineModel_t *)model->data);
			break;
		case CLIP_MODEL_STATIC:
			CM_TraceThroughStaticModel(&tw, (cmStaticModel_t *)model->data);
			break;
		case CLIP_MODEL_DYNAMIC:
			CM_TraceThroughDynamicModel(&tw, (cmDynamicModel_t *)model->data);
			break;
		}
	}
	else
		CM_TraceThroughWorld(&tw, 0, tw.start, tw.end, 0.0f, 1.0f);

	// If there was a collision, transform the plane into world space
	if (tw.trace.fraction != 1.0f){
		if (rotated){
			tmp = tw.trace.c.plane.normal;
			modelAxis.UnprojectVector(tmp, tw.trace.c.plane.normal);
		}

		tw.trace.c.plane.dist += modelOrigin.Dot(tw.trace.c.plane.normal);
	}

	// Calculate end position from the original, unmodified start/end
	tw.trace.endPos.Lerp(start, end, tw.trace.fraction);

	return tw.trace;
}
